A. Technical Field
The present invention pertains generally to data processing, and relates more particularly to profile data structures.
B. Background of the Invention
Profiles have been used to represent time-related data. For example, profiles have been used to represent dynamic supply chain components, such as buffer plans and resource plans. Dynamic supply chain systems are useful tools to help plan materials/inventory, capacity (such as workforce and equipment availability), or both. These systems are beneficial because they can help address complex supply chain issues. However, planning typically involves extensive searching and updating of profiles. Because the profiles are frequently searched, frequently altered, or both, efficient profile representations are important to performance. Traditionally, time varying profiles, such as material profiles and capacity profiles, have been represented using one of two types of data structures: linear linked lists and binary trees.
Supply chain profile information is usually represented using linear linked list data structures. A linked list is a data structure formed of a linear sequence of data records. FIG. 1 graphically depicts the structure of a linked list. Each record or node contains a link or reference to the next record in the sequence. For example, in a supply chain, a set of linked records might represent the inventory of a material over a period of time. Each record might represent a day, the inventory level that day, and a link the next day's record. Although such data structures are simple to implement, they have some drawbacks. First, an alteration in one record creates a domino or cascading effect in which all of the subsequent records in the linked list must also be updated. For example, in FIG. 1, if Record 2 is updated, then Record 3 through Record n must also be updated. Although this is simple, it can be computationally expensive. Second, linked lists are not very efficient for searching. Typically, all or almost all of the records must be searched. For example, if a planner wants to know when an inventory level drops below a threshold level, all of the records will need to be searched. Thus, although a linear data structure can provide simplicity, it creates computational expense in both updating the data records and in searching the data records.
The other data structure approach for time-related profiles has been to use binary trees. FIG. 2 graphically depicts an example of a binary tree structure. Binary trees allows for search space pruning techniques that can be used by heuristics to quickly search by eliminating alternate paths. By way of comparison, linked lists have O(n) complexity, but binary search trees have O(log n) complexity. However, binary trees present a tradeoff. The increased searching ability comes at the cost of added complexity. This complexity is particularly acute when having to update the data. In order to maintain good searching characteristics, the binary tree must be rebalanced if nodes are added or deleted from the tree structure. Rebalancing can be complex and computationally expensive.
Thus, previous attempts to develop a hierarchy for time-related data have only yielded systems with notable drawbacks.